The present invention relates to processors, and more specifically, to branch prediction.
Many processors use algorithms to predict branches in the instruction stream. Branch prediction predicts if branches will deviate from the sequential stream, and if so also predicts where the new non-sequential instruction stream begins. The predictions improve the processor performance by allowing for speculative execution, which avoids stalling execution for branch resolution and target address determination.
Bimodal predictors use branch history tables (BHT) to predict branches. However, bimodal predictors loose accuracy when they attempt to predict branches that exhibit changing behavior such as, branches with different resolution or target addresses.
Pattern history tables (PHT) have been used to detect patterns in the instruction stream and use those detected patterns to more efficiently predict branches that exhibit changing behavior. PHTs ideally track all unique paths of instructions that lead to the branch to achieve accurate branch prediction.